#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

class Code06_LongestValidParentheses
{
public:
    // 时间复杂度O(n)，n是str字符串的长度
    static int longestValidParentheses(string str)
    {
        int n = str.length();
        // dp[0...n-1]
        // dp[i] : 子串必须以i位置的字符结尾的情况下，往左整体有效的最大长度
        vector<int> dp(n, 0);
        int ans = 0;
        for (int i = 1; i < n; i++)
        {
            if (str[i] == ')')
            {
                int p = i - dp[i - 1] - 1; // p是匹配的'('的位置
                //  ?         )
                //  p         i
                if (p >= 0 && str[p] == '(')
                {
                    dp[i] = dp[i - 1] + 2 + (p - 1 >= 0 ? dp[p - 1] : 0);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

int main()
{
    string str = "(()))())(";
    int result = Code06_LongestValidParentheses::longestValidParentheses(str);

    // 输出结果
    cout << "The length of the longest valid parentheses substring is: " << result << endl;

    return 0;
}
